package com.zhang.homework.quicksort;

import com.zhang.sort.MergeSort;

import java.util.*;

/**
 * @author zhang
 * @time 2022/02/12 14:24:50
 */

public class Test {
    public static List<Integer> quickSortGao(List<Integer> list){
        if (list.size() < 2) {
            return list;
        }

        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> middle = new ArrayList<>();

        //分——————————————————————————————————
        //把链表最后一位作为pivot
        Integer pivot = list.get(list.size()-1);
        //把比pivot小的放在左边的list中
        //把比pivot大的放在右边的list中
        for (Integer integer : list) {
            if (integer < pivot) {
                left.add(integer);
            } else if(integer > pivot){
                right.add(integer);
            }else {
                middle.add(integer);
            }

        }

        //合——————————————————————————————————
        list.clear();
        //再对左右链表进行递推排序,要注意回归的顺序先左再middle再右
        list.addAll(quickSortGao(left));
        list.addAll(middle);
        list.addAll(quickSortGao(right));
        return list;



    }

    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }

    private static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        //partition
        int boundary = partition(array, start, end);
        //sortleft
        quickSort(array,start,boundary -1);
        //sortright
        quickSort(array,boundary+1,end);
        System.out.println(Arrays.toString(array));
    }

    private static int partition(int[] array, int start, int end) {
        int pivot = array[end];
        int boundary = start - 1;
        for (int i = start; i <= end; i++) {
            if (array[i] <= pivot) {
                swap(array,i,++boundary);
            }
        }
        return boundary;

    }

    public static void swap(int[] array, int index1,int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    public static int[] getRandomArray(int size,int min,int max) {
        int[] array = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            //得到左闭右闭的区间
            array[i] =  random.nextInt(max)%(max-min+1)+min;
        }
        return array;
    }

    public static void main(String[] args) {
        int[] randomArray = getRandomArray(10, 1, 100);
        System.out.println(Arrays.toString(randomArray));
        //quickSort(randomArray);
        List<Integer> integers = new ArrayList<>(Arrays.asList(1, 25, 89, 32, 2, 14,100,4,4,2));
//        System.out.println(integers);
//        List<Integer> integers1 = quickSortGao(integers);
//        Sysem.out.println(integers1);
        quickSort(randomArray);



    }
}
